home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1999 March / EnigmA AMIGA RUN 35 (1999)(G.R. Edizioni)(IT)[!][issue 1999-03].iso / earcd / devel / vbcc-src / cp.c < prev    next >
C/C++ Source or Header  |  1999-01-01  |  11KB  |  320 lines
  1. /*  $VER: vbcc (cp.c) V0.4     */
  2. /*  verfuegbare Kopien und copy propagation */
  3.  
  4. #include "opt.h"
  5.  
  6. static char FILE_[]=__FILE__;
  7.  
  8. /*  fuer verfuegbare Kopien */
  9. unsigned int ccount;
  10. size_t csize;
  11. struct IC **clist;
  12.  
  13. /*  alle Assignments, globaler oder Adr. fuer propagation etc.         */
  14. unsigned char *cp_globals,*cp_address,*cp_statics,*cp_drefs,*cp_act,*cp_dest;
  15. /*  alle Kopieranweisungen, die eine best. Variable als Quelle haben    */
  16. unsigned char **copies;
  17.  
  18. void available_copies(struct flowgraph *fg)
  19. /*  berechnet die verfuegbaren Kopien fuer jeden Block      */
  20. {
  21.     struct flowgraph *g;struct IC *p;unsigned char *tmp;
  22.     int changed,pass,i,j;
  23.     /*  cp_gen und cp_kill fuer jeden Block berechnen   */
  24.     if(DEBUG&1024) printf("analysing available copies\n");
  25.     tmp=mymalloc(csize);
  26.     for(g=fg;g;g=g->normalout){
  27.         g->cp_in=mymalloc(csize);
  28.         memset(g->cp_in,0,csize);
  29.         g->cp_out=mymalloc(csize);
  30.         memset(g->cp_out,0,csize);
  31.         g->cp_gen=mymalloc(csize);
  32.         memset(g->cp_gen,0,csize);
  33.         g->cp_kill=mymalloc(csize);
  34.         memset(g->cp_kill,0,csize);
  35.         for(p=g->end;p;p=p->prev){
  36.             memset(tmp,0,csize);
  37.             for(j=0;j<p->change_cnt;j++){
  38.                 i=p->change_list[j].v->index;
  39.                 if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
  40.                 if(i>=vcount) continue;
  41.                 bvunite(tmp,copies[i],csize);
  42.             }
  43.             i=p->copyindex;
  44.             if(i>=0&&!BTST(g->cp_kill,i)) BSET(g->cp_gen,i);
  45.             bvdiff(tmp,g->cp_gen,csize);
  46.             bvunite(g->cp_kill,tmp,csize);
  47.  
  48.             if(p==g->start) break;
  49.         }
  50.         if(g==fg){
  51.             memset(g->cp_in,0,csize);
  52.             memcpy(g->cp_out,g->cp_gen,csize);
  53.         }else{
  54.             memset(g->cp_out,UCHAR_MAX,csize);
  55.             bvdiff(g->cp_out,g->cp_kill,csize);
  56.         }
  57.     }
  58.     /*  cp_in und cp_out fuer jeden Block berechnen */
  59.     /*  out(b)=U-gen(B) vorinitialisiert und        */
  60.     /*  in(B0)=0, out(B0)=gen(B0)                   */
  61.     if(DEBUG&1024) {printf("pass:");pass=0;}
  62.     do{
  63.         if(DEBUG&1024) {printf(" %d",++pass);fflush(stdout);}
  64.         changed=0;
  65.         g=fg->normalout;    /*  in B0 aendert sich nichts   */
  66.         while(g){
  67.             struct flowlist *lp;
  68.             /*  in(B)=Schnitt out(P) mit P Vorgaenger von B */
  69.             lp=g->in;
  70.             i=0;    /*  Flag fuer ersten Vorgaenger */
  71.             while(lp){
  72.                 if(!lp->graph) ierror(0);
  73.                 if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
  74.                     if(i){
  75.                         bvintersect(g->cp_in,lp->graph->cp_out,csize);
  76.                     }else{
  77.                         memcpy(g->cp_in,lp->graph->cp_out,csize);i=1;
  78.                     }
  79.                 }
  80.                 lp=lp->next;
  81.             }
  82.             /*  out(b)=gen(B) U (in(B)-kill(B)  */
  83.             memcpy(tmp,g->cp_in,csize);
  84.             bvdiff(tmp,g->cp_kill,csize);
  85.             bvunite(tmp,g->cp_gen,csize);
  86.             if(!bvcmp(tmp,g->cp_out,csize)){changed=1;memcpy(g->cp_out,tmp,csize);}
  87.             g=g->normalout;
  88.         }
  89.     }while(changed);
  90.     if(DEBUG&1024) printf("\n");
  91.     free(tmp);
  92. }
  93.  
  94. int compare_cp(const void *a1,const void *a2)
  95. /*  Stub fuer compare_objs, damit als Vergleichsfunktion fuer qsort geht */
  96. {
  97.     struct IC *p1,*p2;int i1,i2;
  98.     p1=*((struct IC **)a1);p2=*((struct IC **)a2);
  99.     if(!p1||!p2) ierror(0);
  100.     i1=p1->typf; i2=p2->typf;
  101.     if(i1<i2) return(-1);
  102.     if(i1>i2) return(1);
  103.     i1=compare_objs(&p1->q1,&p2->q1,p1->typf);
  104.     if(i1) return(i1);
  105.     i1=compare_objs(&p1->z,&p2->z,p1->typf);
  106.     return(i1);
  107. }
  108.  
  109. void num_copies(void)
  110. /*  numeriert alle einfachen Kopieranweisungen  */
  111. {
  112.     struct IC *p;struct Var *v;int i,n,c;
  113.     if(DEBUG&1024) printf("numerating copies loop1\n");
  114.     ccount=0;
  115.     for(p=first_ic;p;p=p->next){
  116.         if(p->code==ASSIGN&&(p->q1.flags&(VAR/*|VARADR*/))==VAR) p->copyindex=ccount++;
  117.             else            p->copyindex=-1;
  118.     }
  119.     csize=(ccount+CHAR_BIT-1)/CHAR_BIT;
  120.     if(DEBUG&1024) printf("ccount=%lu, csize=%lu\n",(unsigned long)ccount,(unsigned long)csize);
  121.     clist=mymalloc(ccount*sizeof(struct IC *));
  122.     cp_globals=mymalloc(csize);
  123.     memset(cp_globals,0,csize);
  124.     cp_statics=mymalloc(csize);
  125.     memset(cp_statics,0,csize);
  126.     cp_address=mymalloc(csize);
  127.     memset(cp_address,0,csize);
  128.     cp_drefs=mymalloc(csize);
  129.     memset(cp_drefs,0,csize);
  130.     copies=mymalloc(vcount*sizeof(unsigned char *));
  131.     if(DEBUG&1024){ printf("num_copies loop2\n");}
  132.     for(p=first_ic;p;p=p->next){
  133.         if(p->copyindex>=0){
  134.             clist[p->copyindex]=p;
  135.         }
  136.     }
  137.     if(DEBUG&1024){ printf("sorting copies\n");}
  138.     if(ccount>1) qsort(clist,ccount,sizeof(struct IC *),compare_cp);
  139.     if(DEBUG&1024){ printf("renumbering copies\nnum_copies loop3\n");}
  140.     if(ccount>0){   /*  Aufpassen, da ccount unsigned!  */
  141.         for(c=0;c<ccount-1;c++){
  142.             if(!compare_cp(&clist[c],&clist[c+1]))
  143.                 clist[c+1]->copyindex=clist[c]->copyindex;
  144.         }
  145.     }
  146.     if(DEBUG&1024) printf("re-sorting copies\n");
  147.     /*  wieder in die richtige Reihenfolge bringen  */
  148.     for(p=first_ic;p;p=p->next)
  149.         if(p->copyindex>=0) clist[p->copyindex]=p;
  150.  
  151.     for(i=0;i<vcount;i++){
  152.         copies[i]=mymalloc(csize);
  153.         memset(copies[i],0,csize);
  154.     }
  155.  
  156.     if(DEBUG&1024) printf("numerating copies loop4\n");
  157.     for(p=first_ic;p;p=p->next){
  158.         i=p->copyindex;
  159.         if(i>=0){
  160. /*            clist[i]=p;*/
  161.             v=p->z.v;
  162.             n=v->index;
  163.             if(p->z.flags&DREFOBJ) n+=vcount-rcount;
  164.             if(n<0||n>=vcount) ierror(0);
  165.             BSET(copies[n],i);
  166.             if(v->nesting==0||v->storage_class==EXTERN) BSET(cp_globals,i);
  167.             if(p->z.flags&DREFOBJ) BSET(cp_drefs,i);
  168.             if(v->storage_class==STATIC) BSET(cp_statics,i);
  169.             if(v->flags&USEDASADR) BSET(cp_address,i);
  170.             v=p->q1.v;
  171.             n=v->index;
  172.             if(p->q1.flags&DREFOBJ) n+=vcount-rcount;
  173.             if(n<0||n>=vcount){pric2(stdout,p);printf("n=%d\n",n); ierror(0);}
  174.             BSET(copies[n],i);
  175.             if(v->nesting==0||v->storage_class==EXTERN) BSET(cp_globals,i);
  176.             if(p->q1.flags&DREFOBJ) BSET(cp_drefs,i);
  177.             if(v->storage_class==STATIC) BSET(cp_statics,i);
  178.             if(v->flags&USEDASADR) BSET(cp_address,i);
  179.  
  180.         }
  181.     }
  182.     if(DEBUG&2048){
  183.         printf("copy instructions:\n");
  184.         for(i=0;i<ccount;i++){
  185.             printf("%3d: ",i);pric2(stdout,clist[i]);
  186.             if(clist[i]->copyindex!=i) ierror(0);
  187.         }
  188.     }
  189. }
  190. void print_cp(unsigned char *cp)
  191. {
  192.     int i;
  193.     if(!cp) printf("available copies not available\n");
  194.     for(i=0;i<ccount;i++)
  195.         if(BTST(cp,i)){printf("%3d: ",i);pric2(stdout,clist[i]);}
  196. }
  197. int cprop(struct obj *o,int target,zlong size)
  198. /*  ersetzt gegebenenfalls  Kopien, noch aendern, so dass Pointer in DREFOBJS ersetzt werden wie bei target */
  199. {
  200.   struct IC *p,*f=0;int i;struct Var *old;
  201.   old=o->v;
  202.   i=old->index;
  203.   if(!target&&(o->flags&DREFOBJ)) i+=vcount-rcount;
  204.   if(i<0||i>=vcount) ierror(0);
  205.   memcpy(tmp,cp_act,csize);
  206.   bvintersect(tmp,copies[i],csize);
  207.   /*  waehrend diesem Durchlauf geaenderte Kopieranweisungen lieber nicht */
  208.   /*  beachten                                                            */
  209.   bvdiff(tmp,cp_dest,csize);
  210.   for(i=0;i<ccount;i++){
  211.     if(BTST(tmp,i)){
  212.       p=clist[i];
  213.       if(p->z.v==o->v
  214.      &&(zleqto(size,l2zl(0L))||zleqto(size,p->q2.val.vlong))
  215.      &&p->q1.v!=o->v&&zleqto(p->z.val.vlong,o->val.vlong)
  216.      &&((o->v->vtyp->flags&NQ)<=POINTER||(p->typf&NQ)==(o->v->vtyp->flags&NQ))
  217.      ){
  218.     if(((o->flags&DREFOBJ)&&!(p->q1.flags&DREFOBJ))||!(p->q1.flags&DREFOBJ)){
  219.       if(DEBUG&1024){ printf("can replace <%s> by copy:\n",o->v->identifier);pric2(stdout,clist[i]);}
  220.       *o=p->q1;
  221.       if(target){
  222.         o->flags|=DREFOBJ;
  223.         if((o->flags&(VARADR|DREFOBJ))==(VARADR|DREFOBJ))
  224.           o->flags&=~(VARADR|DREFOBJ);
  225.         /*  Wenn eine Variable, dadurch zu einer DREF-Variable  */
  226.         /*  wird, muss num_vars spaeter erneut gemacht werden   */
  227.         if(o->v->index>=rcount){
  228.           update_alias(old,o->v);
  229.           return(2);
  230.         }
  231.       }
  232.       return(1);
  233.     }
  234.       }
  235.     }
  236.   }
  237.   return(0);
  238. }
  239. int copy_propagation(struct flowgraph *fg,int global)
  240. /*  gibt Kopien weiter  */
  241. {
  242.     struct flowgraph *g; struct obj old;int or;
  243.     struct IC *p;struct Var *v;int i,changed,r,j;
  244.     if(DEBUG&1024) printf("searching copies\n");
  245.     cp_act=mymalloc(csize);
  246.     cp_dest=mymalloc(csize);
  247.     memset(cp_dest,0,csize);
  248.     tmp=mymalloc(csize);
  249.     g=fg;changed=0;
  250.     while(g){
  251.         if(!global) memset(cp_act,0,csize); else memcpy(cp_act,g->cp_in,csize);
  252.         p=g->start;
  253.         while(p){
  254.             zlong size;
  255.             if(p->code==ASSIGN||p->code==PUSH) size=p->q2.val.vlong;
  256.                 else size=l2zl(0L);
  257. /*            print_cp(cp_act); pric2(stdout,p);*/
  258.             r=0;
  259.             if(p->code!=ADDRESS&&p->code!=NOP){
  260.                 if((p->q1.flags&(VAR|VARADR))==VAR){
  261.                     r|=cprop(&p->q1,0,size);
  262.                     if(p->q1.flags&DREFOBJ) r|=cprop(&p->q1,1,0);
  263.                 }
  264.                 if((p->q2.flags&(VAR|VARADR))==VAR){
  265.                 /*  passt auf, dass USEQ2ASZ nicht verletzt wird, ist dabei */
  266.                 /*  aber nicht sehr effizient (evtl. koennte kommutiert     */
  267.                 /*  werden, o.ae.)                                          */
  268.                     if(!USEQ2ASZ){ old=p->q2;or=r;}
  269.                     r|=cprop(&p->q2,0,size);
  270.                     if(p->q2.flags&DREFOBJ) r|=cprop(&p->q2,1,0);
  271.                     if(!USEQ2ASZ&&!compare_objs(&p->q2,&p->z,p->typf)){
  272.                         if(DEBUG&1024) printf("copy propagation taken back, because of USEQ2ASZ\n");
  273.                         p->q2=old;
  274.                         r=or;
  275.                     }
  276.                 }
  277.                 if((p->z.flags&(VAR|VARADR|DREFOBJ))==(VAR|DREFOBJ)){
  278.                 /*  passt auf, dass USEQ2ASZ nicht verletzt wird, ist dabei */
  279.                 /*  aber nicht sehr effizient (evtl. koennte kommutiert     */
  280.                 /*  werden, o.ae.                                           */
  281.                     if(!USEQ2ASZ){ old=p->z;or=r;}
  282.                     r|=cprop(&p->z,1,0);
  283.                     if(!USEQ2ASZ&&!compare_objs(&p->q2,&p->z,p->typf)){
  284.                         if(DEBUG&1024) printf("copy propagation taken back, because of USEQ2ASZ\n");
  285.                         p->z=old;
  286.                         r=or;
  287.                     }
  288.                 }
  289.             }
  290.             if(r&&p->copyindex>=0) BSET(cp_dest,p->copyindex);
  291.             changed|=r;
  292.  
  293.             for(j=0;j<p->change_cnt;j++){
  294.                 i=p->change_list[j].v->index;
  295.                 if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
  296.                 if(i>=vcount) continue;
  297.                 bvdiff(cp_act,copies[i],csize);
  298.             }
  299.             if(p->copyindex>=0) BSET(cp_act,p->copyindex);
  300.  
  301.             if(p==g->end) break;
  302.             p=p->next;
  303.         }
  304.         g=g->normalout;
  305.     }
  306.     free(cp_act);
  307.     free(cp_dest);
  308.     free(tmp);
  309.     free(clist);
  310.     free(cp_globals);
  311.     free(cp_statics);
  312.     free(cp_address);
  313.     free(cp_drefs);
  314.     for(i=0;i<vcount;i++) free(copies[i]);
  315.     free(copies);
  316.     gchanged|=changed;
  317.     return(changed);
  318. }
  319.  
  320.